Computerized systems commonly include caches to provide efficient access to stored data. With a typical cache, selected data stored on slower media with higher capacity are loaded onto faster media with lower capacity. For example, data stored on a disk may be pre-fetched and brought into a portion of memory (a cache), where the data may be accessed quickly and efficiently by running programs.
Caches are typically operated at or near their full data capacity. Once a cache becomes full, new data cannot be added to the cache, e.g., in response to a pre-fetch operation, until other data are removed. Various protocols for removing data from a cache, i.e., “data replacement protocols,” are known in the art, and include, for example, least recently used (LRU), first in first out (FIFO), random replacement, and relative distance to logical block address (LBA).
Because a cache stores much less data than the media it supports, access by running programs to desired data in the cache sometimes results in the desired data being found in the cache (a “cache hit”) but sometimes results in the desired data being absent from the cache (a “cache miss”).
Caches are sometimes constructed in multiple levels. For example, a first level of a cache may be very fast, a second level may be slower, and a third level may be slower still. Requests for data from the cache may first query the fastest level and may then query each slower level in turn, from faster to slower, until the requested data is found. Requests for data thus result in cache hits or misses for the multi-level cache as a whole. Such requests may also result in cache hits or misses for individual levels of the multi-level cache. The different levels of a multi-level cache are sometimes referred to in the art as “tiers.”